package year2023.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class Code02_EveryStepShowBoss {

    //抽奖系统
    /*
    * 给定一个整形数组int[] arr 和一个布尔类型数组 boolean[] op
    * 两个数组一定等长,假设长度为N,arr[i]表示客户编号, op[i]表示客户操作
    * arr = [ 3 , 3 , 1 , 2 , 1 , 2 , 5....
    * op  = [ T , T , T , T , F , T , F....
    * 依次表示:3用户购买了一件商品，1用户退货了一件商品...
    * */

    public static class Customer{
        public int id;
        public int buy;
        public int enterTime;

        public Customer(int v, int b, int o){
            id = v;
            buy = b;
            enterTime = 0;
        }
    }

    public static class CandidateComparator implements Comparator<Customer>{

        @Override
        public int compare(Customer o1, Customer o2){
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
        }
    }

    public static class DaddyComparator implements Comparator<Customer>{

        @Override
        public int compare(Customer o1, Customer o2){
            return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
        }
    }

    //暴力解
    public static List<List<Integer>> compare(int[] arr, boolean[] op, int k){
        HashMap<Integer, Customer> map = new HashMap<>();
        ArrayList<Customer> cands = new ArrayList<>();
        ArrayList<Customer> daddy = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < arr.length; i++){
            int id = arr[i];
            boolean buyOrRefund = op[i];
            if (!buyOrRefund && !map.containsKey(id)){
                ans.add(getCurAns(daddy));
                continue;
            }
            //没有发生用户购买为O并且又退货事件
            //1.用户之前购买数是0,此时买货事件
            //2.用户之前购买数>0,此时买货事件
            //3.用户之前购买数>0,此时退货事件
            if (!map.containsKey(id)){
                map.put(id, new Customer(id, 0, 0));
            }
            // 考虑买 还是 卖
            Customer c = map.get(id);
            if (buyOrRefund){
                c.buy++;
            } else {
                c.buy--;
            }
            //用户购买数为0
            if (c.buy == 0){
                map.remove(id);
            }
            //所有表都要删掉
            if (!cands.contains(c) && !daddy.contains(c)){
                if (daddy.size() < k){
                    c.enterTime = i;
                    daddy.add(c);
                }else {
                    c.enterTime = i;
                    cands.add(c);
                }
            }
            cleanZeroBuy(cands);
            cleanZeroBuy(daddy);
            cands.sort(new CandidateComparator());
            daddy.sort(new DaddyComparator());
            move(cands, daddy, k, i);
            ans.add(getCurAns(daddy));

        }
        return ans;
    }

    public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time){
        //候选区为空
        if (cands.isEmpty()){
            return;
        }
        //候选区不为空
        if (daddy.size() < k){
            Customer c = cands.get(0);
            c.enterTime = time;
            daddy.add(c);
            cands.remove(0);
        }else {//得奖区满了，候选区有东西
            if (cands.get(0).buy > daddy.get(0).buy){
                Customer oldDaddy = daddy.get(0);
                daddy.remove(0);
                Customer newDaddy = cands.get(0);
                cands.remove(0);
                newDaddy.enterTime = time;
                oldDaddy.enterTime = time;
                daddy.add(newDaddy);
                cands.add(oldDaddy);
            }
        }
    }

    public static void cleanZeroBuy(ArrayList<Customer> arr){
        List<Customer> noZero = new ArrayList<Customer>();
        for (Customer c : arr){
            if (c.buy != 0){
                noZero.add(c);
            }
        }
        arr.clear();
        for (Customer c : noZero){
            arr.add(c);
        }
    }

    public static List<Integer> getCurAns(ArrayList<Customer> daddy){
        List<Integer> ans = new ArrayList<>();
        for (Customer c : daddy) {
            ans.add(c.id);
        }
        return ans;
    }

    //加强堆优化
    public static class WhosYourDaddy{
        private HashMap<Integer, Customer> customers;
        private HeapGreater<Customer> candHeap;
        private HeapGreater<Customer> daddyHeap;
        private final int daddyLimit;

        public WhosYourDaddy(int limit){
            customers = new HashMap<Integer, Customer>();
            candHeap = new HeapGreater<>(new CandidateComparator());
            daddyHeap = new HeapGreater<>(new DaddyComparator());
            daddyLimit = limit;
        }

        //当前处理i号事件， arr[i] -> id  buyOrRefund
        public void operate(int time, int id, boolean buyOrRefund){
            if (!buyOrRefund && !customers.containsKey(id)){
                return;
            }
            if (!customers.containsKey(id)){
                customers.put(id, new Customer(id, 0, 0));
            }
            Customer c = customers.get(id);
            if (buyOrRefund){
                c.buy++;
            }else {
                c.buy--;
            }
            if (c.buy == 0){
                customers.remove(id);
            }
            if (!candHeap.contains(c) && !daddyHeap.contains(c)){
                if (daddyHeap.size() < daddyLimit){
                    c.enterTime = time;
                    daddyHeap.push(c);
                }else {
                    c.enterTime = time;
                    candHeap.push(c);
                }
            }else if (candHeap.contains(c)){
                if (c.buy == 0){
                    candHeap.remove(c);
                }else {
                    candHeap.resign(c);
                }
            }else {
                if (c.buy == 0){
                    daddyHeap.remove(c);
                }else {
                    daddyHeap.resign(c);
                }
            }
            daddyMove(time);
        }

        public List<Integer> getDaddies(){
            List<Customer> customers = daddyHeap.getAllElements();
            List<Integer> ans = new ArrayList<>();
            for (Customer c : customers){
                ans.add(c.id);
            }
            return ans;
        }

        private void daddyMove(int time){
            if (candHeap.isEmpty()){
                return;
            }
            if (daddyHeap.size() < daddyLimit){
                Customer p = candHeap.pop();
                p.enterTime = time;
                daddyHeap.push(p);
            }else{
                if (candHeap.peek().buy > daddyHeap.peek().buy){
                    Customer oldDaddy = daddyHeap.pop();
                    Customer newDaddy = candHeap.pop();
                    oldDaddy.enterTime = time;
                    newDaddy.enterTime = time;
                    daddyHeap.push(newDaddy);
                    candHeap.push(oldDaddy);
                }
            }
        }


    }

    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k){
        List<List<Integer>> ans = new ArrayList<>();
        WhosYourDaddy whosYourDaddies = new WhosYourDaddy(k);
        for (int i = 0; i < arr.length; i++) {
            whosYourDaddies.operate(i, arr[i], op[i]);
            ans.add(whosYourDaddies.getDaddies());
        }
        return ans;
    }




}
